# 维特比算法（Viterbi Algorithm）




# class Node(object):
#     def __init__(self):
#         self.in = list()
#         self.out = list()
#         self.min = 9999
#         self.prev = Node

#     def add_in_edge(self, edge):
#         self.in.append(edge)

#     def add_out_edge(self, edge):
#         self.out.append(edge) 

#     def update_prev(self, prev):
#         self.prev = prev
#         self.min = self.prev.min +    


# class Edge(object):
#     def __init__(self, start, end, weight):
#         self.start = start
#         self.end = end
#         self.weight = weight
#         start.add_out_edge(self)
#         end.add_in_edge(self)

#     def get_start(self):
#         return self.start

#     def get_end(self):
#         return self.end    



# class Net(object):
#     def __init__(self):
#         pass


graph = {}
graph['start'] = {}
graph['start']['shangpin'] = 4.6
graph['shangpin'] = {}
graph['shangpin']['he'] = 0.8
graph['shangpin']['hefu'] = 0.8
graph['he'] = {}
graph['he']['fuwu'] = 0.8
graph['fuwu'] = {}
graph['fuwu']['end'] = 0.8
graph['hefu'] = {}
graph['hefu']['wu'] = 0.1
graph['wu'] = {}
graph['wu']['end'] = 8.9
graph['end'] = {}

costs = {}
costs['shangpin'] = 4.6
costs['he'] = float("inf")
costs['hefu'] = float("inf")
costs['fuwu'] = float("inf")
costs['wu'] = float("inf")
costs['end'] = float("inf")



parents = {}

parents['shangpin'] = "start"
processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:
            costs[n] = new_cost
            parents[n] = node
    processed.append(node)
    node = find_lowest_cost_node(costs)

cur = 'end'
while cur != 'start':    
    parent = parents[cur]    
    print("{}->{}".format(cur, parent))
    cur = parent



print('Done')
print(costs)


